//2670.找出不同元素数目差数组
//https://leetcode.cn/problems/find-the-distinct-difference-array/?envType=daily-question&envId=2024-01-31
class Solution {
public:
    vector<int> distinctDifferenceArray(vector<int>& nums) {
        //[0,i] -  [i+1,n-1]
        int n = nums.size();
        unordered_set<int> hash;
        vector<int> diff(n+1,0); //存储后缀中 [i+1,n-1] 不同元素数
        for(int i = n-1;i>0;--i)
        {
            hash.insert(nums[i]);
            diff[i] = hash.size();
        }
        vector<int> ret;
        hash.clear();
        //正向遍历数组 hash 中存储 [0,i] 中不同的元素数
        // hash.size()-diif[i-1] 就是差数
        for(int i = 0;i<n;++i)
        {
            hash.insert(nums[i]);
            ret.push_back(hash.size()-diff[i+1]);
        }
        return ret;
    }
};
